import java.util.Arrays;

public class PriorityQueue {
    public int[]arrays;
    public int useSize;

    /**
     * 优先级队列的无参构造函数(初始化数组大小为10个整形元素)
     */
    public PriorityQueue(){
        arrays=new int[10];
    }

    /**
     *构造堆
     * @param arr 为传入的构造堆的数组
     */
    public void createHeap(int[]arr){
        for (int i = 0; i < arr.length; i++) {
            arrays[i]=arr[i];
            useSize++;
        }

        for (int root = ((useSize-1)-1)/2; root>=0; root--) {
            int child=root*2+1;
            shiftDown(root,child);
        }
    }

    /**
     * 将当前子树(root)向下调整为最大堆或者最小堆
     * @param root 当前需要向下调整的子树根节点
     * @param child 子树的孩子节点
     */
    public void shiftDown(int root,int child){
            while(child<useSize){
                if(child+1<useSize&&arrays[child+1]>arrays[child]){
                    child=child+1;
                }
                if(arrays[root]<arrays[child]){
                    int temp=arrays[child];
                    arrays[child]=arrays[root];
                    arrays[root]=temp;
                    root=child;
                    child=root*2+1;
                }else{
                    break;
                }

            }

    }

    /**
     * 传入一个值到堆中，并重新调整堆的数据，大致调整思路为
     * 将要插入的值放到堆的最后，然后由于堆在插入该节点之前本来就已经
     * 调整好了，所以此时就只需要对插入的这个节点进行向上调整(shiftUp)
     * @param value 入堆的值
     */
    public void push(int value) throws InterruptedException {
        if(isFull()){
            System.out.println("【-------扩容中--------】");
            //休眠2秒
            Thread.sleep(2000);
            this.arrays= Arrays.copyOf(arrays,arrays.length+5);
            System.out.println("【扩容成功】");
        }
        arrays[useSize]=value;
        shiftUp(useSize);
        useSize++;
    }
    public boolean isFull(){
        return useSize==arrays.length;
    }

    /**
     *向上调整
     * @param child 需要调整的子节点
     */
    public void shiftUp(int child){
        int parent=(useSize-1)/2;
        while(child>0){
            if(arrays[child]>arrays[parent]){
                int temp=arrays[child];
                arrays[child]=arrays[parent];
                arrays[parent]=temp;
                child=parent;
                parent=(child-1)/2;
            }else{
                break;
            }
        }
    }

    /**
     * 获取堆顶元素
     * @return
     */
    public int poll(){
        if(isEmpty()){
            System.out.println("优先队列中无元素");
            return -1;
        }
        return arrays[0];
    }

    public boolean isEmpty(){
        return useSize==0;
    }

    /**
     * 弹出堆顶元素
     * @return
     */
    public int peek(){
        int top=arrays[0];
        int temp=arrays[0];
        arrays[0]=arrays[useSize-1];
        arrays[useSize-1]=temp;
        useSize--;
        shiftDown(0,1);
        return top;
    }

    /**
     * 打印堆中的数据(实现堆的二叉树的层序遍历)
     */
    public void show(){
        for (int i = 0; i < useSize; i++) {
            System.out.print(arrays[i]+" ");
        }
        System.out.println();
    }
}
